/*
 * Copyright (c) 1998, 2013, Oracle and/or its affiliates. All rights reserved.
 * ORACLE PROPRIETARY/CONFIDENTIAL. Use is subject to license terms.
 *
 *
 *
 *
 *
 *
 *
 *
 *
 *
 *
 *
 *
 *
 *
 *
 *
 *
 *
 *
 */

package java.util;

/**
 * 基于TreeMap的NavigableSet实现。
 * 元素使用它们的自然顺序排序，或者通过在设置创建时提供的比较器进行排序，这取决于使用的是哪个构造函数。
 *
 * <p>这个实现为基本操作(add、remove和contains)提供了保证的log(n)时间开销。
 *
 * <p>请注意，如果要正确实现set接口，set维护的顺序(不管是否提供显式比较器)必须与equals一致。
 * (参见Comparable或Comparator获得与equals一致的精确定义。)
 * 这是因为Set接口是根据equals操作定义的，但是TreeSet实例使用它的compareTo(或compare)方法执行所有的元素比较，
 * 所以从Set的角度来看，这个方法认为比较相等的两个元素是equals相等的。
 * 一个集合的行为是定义良好的，即使它的比较顺序与equals不一致;只是没有遵守Set接口的一般约定。
 *
 * <p>注意，这个实现不是同步的。
 * 如果多个线程同时访问树集，并且至少有一个线程修改树集，则必须在外部对树集进行同步。
 * 这通常是通过对一些自然封装了集合的对象进行同步来实现的。
 * 如果不存在这样的对象，则应该使用集合来“包装”。
 * Collections.synchronizedSortedSet方法。这最好在创建时完成，以防止意外的不同步访问集:<pre>
 *   SortedSet s = Collections.synchronizedSortedSet(new TreeSet(...));</pre>
 *
 * <p>这个类的迭代器方法返回的迭代器是快速失效的:
 * 如果在迭代器创建后的任何时候修改集合，除了通过迭代器自己的删除方法之外，迭代器将抛出ConcurrentModificationException。
 * 因此，在面对并发修改时，迭代器会快速而干净地失败，而不是在将来某个不确定的时间冒任意的、不确定的行为的风险。
 *
 * <p>注意，不能保证迭代器的快速故障行为，因为通常来说，在存在非同步并发修改的情况下，不可能做出任何严格的保证。
 * 故障快速迭代器在最大努力的基础上抛出ConcurrentModificationException。
 * 因此，编写一个依赖于这个异常的正确性的程序是错误的:迭代器的快速故障行为应该只用于检测bug。
 *
 * @param <E> the type of elements maintained by this set
 *
 * @author  Josh Bloch
 * @see     Collection
 * @see     Set
 * @see     HashSet
 * @see     Comparable
 * @see     Comparator
 * @see     TreeMap
 * @since   1.2
 */

public class TreeSet<E> extends AbstractSet<E>
    implements NavigableSet<E>, Cloneable, java.io.Serializable
{
    /**
     * 依赖的map
     */
    private transient NavigableMap<E,Object> m;

    // 依赖的map中，关联的value，所有treemap共用一个
    private static final Object PRESENT = new Object();

    /**
     * 构造由指定的navigable映射支持的集合。
     */
    TreeSet(NavigableMap<E,Object> m) {
        this.m = m;
    }

    /**
     * 构造一个新的空树集，根据其元素的自然顺序排序。
     * 所有插入到集合中的元素必须实现Comparable接口。
     * 此外,所有这些元素都必须相互可比:e1.compareTo (e2)不能抛出ClassCastException。
     * 如果用户试图添加一个元素的集合违反这个约束(例如,用户试图添加一个字符串元素的一组元素是整数),添加调用将抛出一个ClassCastException。
     */
    public TreeSet() {
    	// 新建一个treemap作为依赖的map
        this(new TreeMap<E,Object>());
    }

    /**
     * 构造一个新的空树集，根据指定的比较器排序。
     * 所有元素插入到集合必须由指定比较器相互可比:comparator.compare (e1, e2)不能抛出ClassCastException。
     * 如果用户试图添加一个元素的集合违反这个约束,添加调用将抛出一个ClassCastException。
     *
     * @param comparator the comparator that will be used to order this set.
     *        If {@code null}, the {@linkplain Comparable natural
     *        ordering} of the elements will be used.
     */
    public TreeSet(Comparator<? super E> comparator) {
    	// 把comparator传递给treemap
        this(new TreeMap<>(comparator));
    }

    /**
     * 构造一个新树集，其中包含指定集合中的元素，按照其元素的自然顺序排序。
     * 所有插入到集合中的元素必须实现可比接口。
     * 而且，所有这些元素必须是相互可比的:e1. compareto (e2)不能抛出ClassCastException。
     *
     * @param c collection whose elements will comprise the new set
     * @throws ClassCastException if the elements in {@code c} are
     *         not {@link Comparable}, or are not mutually comparable
     * @throws NullPointerException if the specified collection is null
     */
    public TreeSet(Collection<? extends E> c) {
        this();
        addAll(c);
    }

    /**
     * 构造一个包含相同元素的新树集，并使用与指定的已排序集相同的顺序。
     *
     * @param s sorted set whose elements will comprise the new set
     * @throws NullPointerException if the specified sorted set is null
     */
    public TreeSet(SortedSet<E> s) {
        this(s.comparator());
        addAll(s);
    }

    /**
     * 以升序返回此集合中元素的迭代器。
     *
     * @return an iterator over the elements in this set in ascending order
     */
    public Iterator<E> iterator() {
        return m.navigableKeySet().iterator();
    }

    /**
     * 按降序返回该集合中元素的迭代器。
     *
     * @return an iterator over the elements in this set in descending order
     * @since 1.6
     */
    public Iterator<E> descendingIterator() {
        return m.descendingKeySet().iterator();
    }

    /**
     * @since 1.6
     */
    public NavigableSet<E> descendingSet() {
        return new TreeSet<>(m.descendingMap());
    }

    /**
     * 返回此集合中的元素数(其基数)。
     *
     * @return the number of elements in this set (its cardinality)
     */
    public int size() {
        return m.size();
    }

    /**
     * 如果该集合不包含元素，则返回true。
     *
     * @return {@code true} if this set contains no elements
     */
    public boolean isEmpty() {
        return m.isEmpty();
    }

    /**
     * 如果该集合包含指定的元素，则返回true。
     * 更正式地说，当且仅当这个集合包含一个元素e (o==null ?e = = null: o.equals (e))。
     *
     * @param o object to be checked for containment in this set
     * @return {@code true} if this set contains the specified element
     * @throws ClassCastException if the specified object cannot be compared
     *         with the elements currently in the set
     * @throws NullPointerException if the specified element is null
     *         and this set uses natural ordering, or its comparator
     *         does not permit null elements
     */
    public boolean contains(Object o) {
        return m.containsKey(o);
    }

    /**
     * 如果指定的元素尚未出现，则将其添加到此集合。更正式地说，如果集合不包含e2元素，则将指定的元素e添加到该集合中，
     * 使得(e==null ?e2 = = null: e.equals (e2))。如果该集合已经包含元素，则调用将保持集合不变并返回false。
     *
     * @param e element to be added to this set
     * @return {@code true} if this set did not already contain the specified
     *         element
     * @throws ClassCastException if the specified object cannot be compared
     *         with the elements currently in this set
     * @throws NullPointerException if the specified element is null
     *         and this set uses natural ordering, or its comparator
     *         does not permit null elements
     */
    public boolean add(E e) {
    	// 放入e和PRESENT
        return m.put(e, PRESENT)==null;
    }

    /**
     * 如果指定的元素存在，则从该集合中移除它。
     * 更正式地说，如果这个集合包含这样一个元素e (o==null ?e==null: o.equals(e))，那么删除e。
     * 如果该集合包含元素，则返回true(或者，如果该集合由于调用而发生更改，则返回true)。
     * (一旦调用返回，这个集合将不包含元素。)
     *
     * @param o object to be removed from this set, if present
     * @return {@code true} if this set contained the specified element
     * @throws ClassCastException if the specified object cannot be compared
     *         with the elements currently in this set
     * @throws NullPointerException if the specified element is null
     *         and this set uses natural ordering, or its comparator
     *         does not permit null elements
     */
    public boolean remove(Object o) {
        return m.remove(o)==PRESENT;
    }

    /**
     * 从这个集合中移除所有的元素。这个集合在这个调用返回后将是空的。
     */
    public void clear() {
        m.clear();
    }

    /**
     * 将指定集合中的所有元素添加到此集合。
     *
     * @param c collection containing elements to be added to this set
     * @return {@code true} if this set changed as a result of the call
     * @throws ClassCastException if the elements provided cannot be compared
     *         with the elements currently in the set
     * @throws NullPointerException if the specified collection is null or
     *         if any element is null and this set uses natural ordering, or
     *         its comparator does not permit null elements
     */
    public  boolean addAll(Collection<? extends E> c) {
        // 如果合适的话，使用treemap的方法，到达线性时间开销
        if (m.size()==0 && c.size() > 0 &&
            c instanceof SortedSet &&
            m instanceof TreeMap) {
        	// 如果当前m为空，c不为空，c为sortedset，m为treemap
            SortedSet<? extends E> set = (SortedSet<? extends E>) c;
            TreeMap<E,Object> map = (TreeMap<E, Object>) m;
            Comparator<?> cc = set.comparator();
            Comparator<? super E> mc = map.comparator();
            if (cc==mc || (cc != null && cc.equals(mc))) {
            	// 如果m和c的comparator都是null，或者两者相同
                map.addAllForTreeSet(set, PRESENT);
                return true;
            }
        }
        return super.addAll(c);
    }

    /**
     * @throws ClassCastException {@inheritDoc}
     * @throws NullPointerException if {@code fromElement} or {@code toElement}
     *         is null and this set uses natural ordering, or its comparator
     *         does not permit null elements
     * @throws IllegalArgumentException {@inheritDoc}
     * @since 1.6
     */
    public NavigableSet<E> subSet(E fromElement, boolean fromInclusive,
                                  E toElement,   boolean toInclusive) {
    	// 创建新的treeset，依赖的map是原来m的视图
        return new TreeSet<>(m.subMap(fromElement, fromInclusive,
                                       toElement,   toInclusive));
    }

    /**
     * @throws ClassCastException {@inheritDoc}
     * @throws NullPointerException if {@code toElement} is null and
     *         this set uses natural ordering, or its comparator does
     *         not permit null elements
     * @throws IllegalArgumentException {@inheritDoc}
     * @since 1.6
     */
    public NavigableSet<E> headSet(E toElement, boolean inclusive) {
        return new TreeSet<>(m.headMap(toElement, inclusive));
    }

    /**
     * @throws ClassCastException {@inheritDoc}
     * @throws NullPointerException if {@code fromElement} is null and
     *         this set uses natural ordering, or its comparator does
     *         not permit null elements
     * @throws IllegalArgumentException {@inheritDoc}
     * @since 1.6
     */
    public NavigableSet<E> tailSet(E fromElement, boolean inclusive) {
        return new TreeSet<>(m.tailMap(fromElement, inclusive));
    }

    /**
     * @throws ClassCastException {@inheritDoc}
     * @throws NullPointerException if {@code fromElement} or
     *         {@code toElement} is null and this set uses natural ordering,
     *         or its comparator does not permit null elements
     * @throws IllegalArgumentException {@inheritDoc}
     */
    public SortedSet<E> subSet(E fromElement, E toElement) {
        return subSet(fromElement, true, toElement, false);
    }

    /**
     * @throws ClassCastException {@inheritDoc}
     * @throws NullPointerException if {@code toElement} is null
     *         and this set uses natural ordering, or its comparator does
     *         not permit null elements
     * @throws IllegalArgumentException {@inheritDoc}
     */
    public SortedSet<E> headSet(E toElement) {
        return headSet(toElement, false);
    }

    /**
     * @throws ClassCastException {@inheritDoc}
     * @throws NullPointerException if {@code fromElement} is null
     *         and this set uses natural ordering, or its comparator does
     *         not permit null elements
     * @throws IllegalArgumentException {@inheritDoc}
     */
    public SortedSet<E> tailSet(E fromElement) {
        return tailSet(fromElement, true);
    }

    public Comparator<? super E> comparator() {
        return m.comparator();
    }

    /**
     * @throws NoSuchElementException {@inheritDoc}
     */
    public E first() {
        return m.firstKey();
    }

    /**
     * @throws NoSuchElementException {@inheritDoc}
     */
    public E last() {
        return m.lastKey();
    }

    // NavigableSet API methods

    /**
     * @throws ClassCastException {@inheritDoc}
     * @throws NullPointerException if the specified element is null
     *         and this set uses natural ordering, or its comparator
     *         does not permit null elements
     * @since 1.6
     */
    public E lower(E e) {
        return m.lowerKey(e);
    }

    /**
     * @throws ClassCastException {@inheritDoc}
     * @throws NullPointerException if the specified element is null
     *         and this set uses natural ordering, or its comparator
     *         does not permit null elements
     * @since 1.6
     */
    public E floor(E e) {
        return m.floorKey(e);
    }

    /**
     * @throws ClassCastException {@inheritDoc}
     * @throws NullPointerException if the specified element is null
     *         and this set uses natural ordering, or its comparator
     *         does not permit null elements
     * @since 1.6
     */
    public E ceiling(E e) {
        return m.ceilingKey(e);
    }

    /**
     * @throws ClassCastException {@inheritDoc}
     * @throws NullPointerException if the specified element is null
     *         and this set uses natural ordering, or its comparator
     *         does not permit null elements
     * @since 1.6
     */
    public E higher(E e) {
        return m.higherKey(e);
    }

    /**
     * @since 1.6
     */
    public E pollFirst() {
        Map.Entry<E,?> e = m.pollFirstEntry();
        return (e == null) ? null : e.getKey();
    }

    /**
     * @since 1.6
     */
    public E pollLast() {
        Map.Entry<E,?> e = m.pollLastEntry();
        return (e == null) ? null : e.getKey();
    }

    /**
     * 返回此TreeSet实例的浅拷贝。(元素本身不是克隆的。)
     *
     * @return a shallow copy of this set
     */
    @SuppressWarnings("unchecked")
    public Object clone() {
        TreeSet<E> clone;
        // 先浅克隆生成clone
        try {
            clone = (TreeSet<E>) super.clone();
        } catch (CloneNotSupportedException e) {
            throw new InternalError(e);
        }
        // clone的m为新生成的treemap，里面的元素还是原来m的元素
        clone.m = new TreeMap<>(m);
        return clone;
    }

    /**
     * 将TreeSet实例的状态保存到流中(即序列化它)。
     *
     * @serialData Emits the comparator used to order this set, or
     *             {@code null} if it obeys its elements' natural ordering
     *             (Object), followed by the size of the set (the number of
     *             elements it contains) (int), followed by all of its
     *             elements (each an Object) in order (as determined by the
     *             set's Comparator, or by the elements' natural ordering if
     *             the set has no Comparator).
     */
    private void writeObject(java.io.ObjectOutputStream s)
        throws java.io.IOException {
        // Write out any hidden stuff
        s.defaultWriteObject();

        // Write out Comparator
        s.writeObject(m.comparator());

        // Write out size
        s.writeInt(m.size());

        // Write out all elements in the proper order.
        for (E e : m.keySet())
            s.writeObject(e);
    }

    /**
     * 从流中重新构造TreeSet实例(即反序列化它)。
     */
    private void readObject(java.io.ObjectInputStream s)
        throws java.io.IOException, ClassNotFoundException {
        // Read in any hidden stuff
        s.defaultReadObject();

        // Read in Comparator
        @SuppressWarnings("unchecked")
            Comparator<? super E> c = (Comparator<? super E>) s.readObject();

        // Create backing TreeMap
        TreeMap<E,Object> tm = new TreeMap<>(c);
        m = tm;

        // Read in size
        int size = s.readInt();

        tm.readTreeSet(size, s, PRESENT);
    }

    /**
     * 在这个集合的元素上创建一个迟绑定和快速失败的Spliterator。
     *
     * <p>Spliterator报告SIZED，DISTINCT，SORTED，ORDERED。覆盖实现应该记录额外特征值的报告。
     *
     * <p>如果树集的比较器(参见comparator())为空，则spliterator的比较器
     * (参见java.util.Spliterator.getComparator())为空。
     * 否则，spliterator的比较器与树集的比较器具有相同的顺序。
     *
     * @return a {@code Spliterator} over the elements in this set
     * @since 1.8
     */
    public Spliterator<E> spliterator() {
        return TreeMap.keySpliteratorFor(m);
    }

    private static final long serialVersionUID = -2479143000061671589L;
}
